
// 需要做些重构
// 其他链表会继承单项链表，所以单项链表的私有属性要改成特殊的
// 增加tail字段，永远指向最后的节点
// 所以所有对节点的操作都会修改到tail
// 新增节点可以因为tail的出现变得更简单
// 增加一个判断是否最后一个节点的方法，用来优化遍历时候的代码


export class Node<T> {
  data: T;
  next: Node<T> | null;
  constructor(data: T) {
    this.data = data;
    this.next = null;
  }
}

export default class LinedList<T> {
  protected head: Node<T> | null = null;
  protected size: number = 0;
  protected tail: Node<T> | null = null;

  protected getNode(position: number): Node<T> | undefined {
    if (position < 0 || this.size <= position) {
      return undefined;
    }
    let current = this.head!;
    let index = 0;
    while (index < position) {
      current = current.next!;
      index++;
    }
    return current;
  }
  append(item: T): void {
    let newNode = new Node(item);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
    // 新增节点可以因为tail的出现变得更简单
      this.tail!.next = newNode
      this.tail = newNode;
    }
    this.size++;
  }
  traverse(): string {
    let values: T[] = [];
    let current = this.head;
    while (current) {
      values.push(current.data);
      // 增加中断方式
      if(this.isLastNode(current)) break;
      current = current.next;
    }
    return values.join("->");
  }
  insert(position: number, element: T): T | null {
    if(!this.size) return null
    if (position < 0 && position > this.size) {
      return null;
    }
    const newNode = new Node(element);

    if (position === 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      const node = this.getNode(position - 1);
      if (node === undefined) return null;
      newNode.next = node.next;
      node.next = newNode;
      if(position === this.size){
        // 刚好插入尾部的时候，tgail需要更新
        this.tail = newNode
      }
    }

    this.size++;
    return newNode.data;
  }
  update(position: number, element: T): boolean {
    const node = this.getNode(position);
    if (node === undefined) return false;
    node.data = element;
    return true;
  }
  removeAt(position: number): T | undefined {
    if(!this.size) return undefined
    if (position < 0 && position > this.size) return undefined;
    let current = this.head;
    if (position === 0) {
      if(this.size === 1){
        this.head = null;
        this.tail = null
      }else{
      this.head = current!.next;
      }
    } else {
      const preNode = this.getNode(position - 1);
      if (preNode === undefined) return undefined;
      current = preNode.next!;
      preNode.next = preNode.next?.next ?? null;
      if(this.size - 1 === position){
        // 刚好删除最后节点的时候，tail需要更新
        this.tail = preNode        
      }
    }

    this.size--;    
    return current!.data;
  }
  get(position: number): T | undefined {
    return this.getNode(position)?.data;
  }
  isEmpty(): boolean {
    return this.size === 0;
  }

  indexOf(element: T){
    let current = this.head
    let idx = 0
    while(current){
      if(current.data === element){
        return idx;
      }
      if(this.isLastNode(current)) break;
      current = current.next
      idx++
    }
    return -1
  }
  private isLastNode(_node: Node<T>):boolean {
    return this.tail === _node
  }
}

// const linedList1 = new LinedList<string>();

// linedList1.append("a");
// linedList1.append("b");
// linedList1.append("c");
// linedList1.append("d");
// console.log(linedList1.traverse());

// console.log(linedList1.get(0));
// console.log(linedList1.get(1));
// console.log(linedList1.get(2));
// console.log(linedList1.get(3));

// linedList1.insert(2, "嘻");
// console.log(linedList1.traverse());

// linedList1.update(2, "哈");
// console.log(linedList1.traverse());


// console.log(linedList1.removeAt(2));

// console.log(linedList1.traverse());
